#include <stdio.h>
#include <stdint.h>

 
#define MAXNUM  1000  /* list all primes up to MaxNum */
#define NUMITERATIONS 10 /* Repeats procedure NumIterations times*/


int sieve(int numeroMassimo){
	
	int isPrime[numeroMassimo+1];
	
	//isPrime[0] = 0;
	//Inizializzo tutti gli elementi dell'array al valore true
	int j;
	for (j = 1; j <= numeroMassimo; j++){
		isPrime[j] = 1;
	}
	
	int indice = 2;
	int indiceK = 0;
	
	//I numeri primi di un numero N sono compresi tra 1 e SQRT(N)
	while ((indice*indice) <= numeroMassimo){
		
		if (isPrime[indice]){
			
			indiceK = indice + indice;
			
			while (indiceK <= numeroMassimo){
				
				isPrime[indiceK] = 0;
				indiceK = indiceK + indice;
			}
			
		}
		
		indice = indice +1;
		
	}
	
	int numeriPrimi = 0;
	
	for (j = 1; j <= numeroMassimo; j++){
		
		if(isPrime[j]){
			numeriPrimi = numeriPrimi+1;
			//printf("Numero Primo: %d\n", j);
		}
	}
	
	return numeriPrimi;
}
